#include <stdio.h>
#include <stdlib.h>
#define MAX 9999
#define MIN -1

// Structure for both process and hole
struct block
{
	int id;
	int sa;
	int ea;
	struct block *next;
};

// 2 Linked Lists - process & hole
struct block *prcs;
struct block *hole;

// Global Variable to hold fit type
int fit_option;
// Global Varibable to hold total memory size
int tmsize;

// Function to add free memory - hole
void add_hole(int sad,int ead)
{
	struct block *temp,*new;
	temp=hole;
	while(temp->next!=NULL)
	{
		if(temp->next->ea==sad)
		{
			temp->next->ea+=(ead-sad);
			return;
		}
		if(temp->next->sa>sad)	break;
		temp=temp->next;
	}
	new=(struct block*)malloc(sizeof(struct block));
	new->sa=sad;
	new->ea=ead;
	new->next=temp->next;
	temp->next=new;
}

// Function to display status of process & holes
void display_table(void)
{
	int i=0;
	struct block *temp;
	for(i=0;i++<40;printf("-"));
	printf("\n~!~ Free Space Table ~!~");
	printf("\nHole ID\tStart\tEnd\n");
	for(i=0;i++<40;printf("-"));
	temp=hole->next;
	i=0;
	if(temp==NULL)
		printf("\nNo Holes!");
	else
		while(temp!=NULL)
		{
			printf("\n%d\t%d\t%d",++i,temp->sa,temp->ea);
			temp=temp->next;
		}


	printf("\n\n~!~ Allocated Memeory ~!~\n");
	for(i=0;i++<40;printf("-"));
	printf("\nProcess\tPID\tStart\tEnd\n");
	for(i=0;i++<40;printf("-"));
	temp=prcs->next;
	i=0;
	if(temp==NULL)
		printf("\nNo Process!...");
	else
		while(temp!=NULL)
		{
			printf("\n%d\t%d\t%d\t%d",++i,temp->id,temp->sa,temp->ea);
			temp=temp->next;
		}
printf("\n");
for(i=0;i++<40;printf("-"));
printf("\n\n");
}

// Function to add a process given
// starting address,address space & pid
void add_process(int sad,int asp,int pid)
{
      struct block *temp,*new;
      temp=prcs;
      while(temp->next!=NULL)
      {
	      if(temp->next->sa>sad)
		 break;
	      temp=temp->next;
      }
      new=(struct block*)malloc(sizeof(struct block));
      new->sa=sad;
      new->ea=sad+asp;
      new->id=pid;
      new->next=prcs->next;
      prcs->next=new;
}

// Function to delete an block
void delete_block(struct block *delete,struct block *start)
{
	struct block *temp=start;
	while(temp->next!=NULL)
	{
		if(temp->next==delete)
			break;
		temp=temp->next;
	}
	temp->next=delete->next;
	free(delete);
	printf("Deleting block()....");
}

// Start to create NULL nodes
void  initialize(int mem_size)
{
	prcs=(struct block *)malloc(sizeof(struct block));
	prcs->next=NULL;
	hole=(struct block *)malloc(sizeof(struct block));
	hole->next=NULL;
	printf("\nInitialization started...");
	add_hole(0,mem_size);
	printf("\nInitialization Complete...");
}

void first_fit(int asp,int id)
{
	struct block *temp;
	int start;
	temp=hole->next;
	while(temp!=NULL)
	{
		if((temp->ea-temp->sa)>=asp)
			break;
		temp=temp->next;
	}
	if(temp==NULL)
	{
		printf("\nNo Memory left free!");
		return;
	}
	start=temp->sa;
	if((temp->ea-temp->sa)==asp)
		delete_block(temp,hole);
	else
		temp->sa=temp->sa+asp;
	add_process(start,asp,id);
	display_table();
}

void best_fit(int asp,int id)
{
	struct block *temp,*fit;
	int start;
	int space=MAX;
	temp=hole->next;

	if(temp->ea<=tmsize)
	{
	while(temp!=NULL)
	{
		if((temp->ea-temp->sa)>=asp)
			if((temp->ea-temp->sa)<space)
			{
				fit=temp;
				space=temp->ea-temp->sa;
			}
		temp=temp->next;
	}
	if(fit==NULL)
	{
		printf("\nNo Memory left free!");
		return;
	}
	start=fit->sa;
	if((fit->ea-fit->sa)==asp)
		delete_block(fit,hole);
	else
		fit->sa=fit->sa+asp;
	add_process(start,asp,id);
	display_table();
	}
	else
	printf("\nLarge Overflow Exceptions...");
}

void worst_fit(int asp,int id)
{
	struct block *temp,*fit;
	int start;
	int space=MIN;
	temp=hole->next;
	fit=NULL;
	if(temp->ea<=tmsize)
	{
	while(temp!=NULL)
	{
		if((temp->ea-temp->sa)>=asp)
			if((temp->ea-temp->sa)>space)
			{
				fit=temp;
				space=temp->ea-temp->sa;
			}
		temp=temp->next;
	}
	if(fit==NULL)
	{
		printf("\nNo Memory left free!");
		return;
	}
	start=fit->sa;
	if((fit->ea-fit->sa)==asp)
		delete_block(fit,hole);
	else
		fit->sa=fit->sa+asp;
	add_process(start,asp,id);
	display_table();
	}
	else
	printf("\nLarge Overflow Exceptions....");
}

// Fit plan option routine
void fit(int option,int asp,int id)
{
	switch(option)
	{
		case 1: first_fit(asp,id);	break;
		case 2: best_fit(asp,id); 	break;
		case 3: worst_fit(asp,id);	break;
		defalut: printf("Error in passing option...");	break;
	}
}

// Procedure to add a new process
void add_new_process()
{
	int asp,id;
	printf("\nEnter ID");
	scanf("%d",&id);
	printf("\nEnter address space :");
	scanf("%d",&asp);
	if(asp<tmsize)
		fit(fit_option,asp,id);
	else
		printf("\nUnable to handle values >MS....");
}

// Procedure to end the process
void end_process(void)
{
	struct block *temp,*delete;
	delete=hole;
	while(temp!=NULL)
	{
		temp=delete->next;
		free(delete);
		delete=temp;
	}
	delete=prcs;
	while(delete!=NULL)
	{
		temp=delete->next;
		free(delete);
		delete=temp;
	}
}

// Procedure to delete exixting block node
void delete_existing()
{
	int id,sa,ea;
	struct block *temp;
	printf("\nEnter the process id :");
	scanf("%d",&id);
	temp=prcs->next;
	while(temp!=NULL)
	{
		if(temp->id==id)
			break;
		temp=temp->next;
	}
	if(temp==NULL)
	{
		printf("\nNope...No Process ~!~");
		return;
	}
	sa=temp->sa;
	ea=temp->ea;
	delete_block(temp,prcs);
	add_hole(sa,ea);
	display_table();
}

void run_fit(void)
{
	int choice;
	while(1)
	{
	printf("\n\nMemory Management");
	printf("\n1.Add Process\n2.Remove Process\n3.Quit Areana\n?:");
	scanf("%d",&choice);
	switch(choice)
		{
			case 1:	add_new_process();
				break;
			case 2: delete_existing();
				break;
			case 3:	end_process();
				exit(0);
		}
	}
}

void choose_fit()
{
	int option;
	printf("\n\nEnter your Choice:");
	printf("\n1.First Fit\n2.Best Fit\n3.Worst Fit\n?:");
	scanf("%d",&option);
	switch(option)
	{
		case 1: fit_option = 1;	break; // FF
		case 2: fit_option = 2; break; // BF
		case 3: fit_option = 3; break; // WF
		defalut: printf("\nWrong Entry...");  break;
	}
}

main()
{
	int choice;
	printf("\nEnter total memory size : ");
	scanf("%d",&tmsize);
	initialize(tmsize);
	choose_fit();
	run_fit();
	return 0;
}